package heapSort;

import java.util.List;

/**
 * 此类实现堆排序
 * 大顶堆排序 其中核心为下滤过程
 */
public class HeapSort {

    /**
     * 实现堆排序的方法
     * @param list 传入需要排序的集合
     * @return 返回排序好的集合
     */
    public static List<Integer> heapSort(List<Integer> list) {
        //当前折半的原因 现将当前数组看成二叉树 中间位置一定不是叶子结点
        for (int i = (list.size()-2)/2; i >= 0 ; i--) {
            adjustHeap(list,i,list.size());
        }
        //构建完成大顶堆之后 顶堆元素和堆末元素交换 在执行构建大顶堆操作
        for (int i = list.size() - 1; i > 0; i--) {
            Integer integer = list.get(i);
            list.set(i,list.get(0));
            list.set(0,integer);
            adjustHeap(list,0,i);
        }
        return list;
    }

    /**
     * 构建大顶堆
     * @param list 需要构建大顶堆的集合
     * @param i 非叶子结点的下标
     * @param size 集合大小
     */
    private static void adjustHeap(List<Integer> list, int i, int size) {
        //存储父节点的值 用于最后的复制
        Integer integer = list.get(i);
        //计算父节点的右孩子 平衡二叉树特性
        int childIndex = 2 * i + 1;
        while (childIndex < size){
            //存在右孩子 并且右孩子大于左孩子 定位右孩子
            if (childIndex + 1 < size && list.get(childIndex + 1) > list.get(childIndex)){
                childIndex ++;
            }
            //如果父节点比两个孩子都大
            if (integer >= list.get(childIndex)){
                break;
            }
            //单向赋值
            list.set(i,list.get(childIndex));
            i = childIndex;
            childIndex = 2 * childIndex + 1;
        }
        list.set(i,integer);
    }

}
